Search Results

Documents authored by Durand, Bruno

Document
DOI: 10.4230/LIPIcs.MFCS.2017.5
On the Expressive Power of Quasiperiodic SFT

Authors: Bruno Durand and Andrei Romashchenko

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
In this paper we study the shifts, which are the shift-invariant and topologically closed sets of configurations over a finite alphabet in Z^d. The minimal shifts are those shifts in which all configurations contain exactly the same patterns. Two classes of shifts play a prominent role in symbolic dynamics, in language theory and in the theory of computability: the shifts of finite type (obtained by forbidding a finite number of finite patterns) and the effective shifts (obtained by forbidding a computably enumerable set of finite patterns). We prove that every effective minimal shift can be represented as a factor of a projective subdynamics on a minimal shift of finite type in a bigger (by 1) dimension. This result transfers to the class of minimal shifts a theorem by M.Hochman known for the class of all effective shifts and thus answers an open question by E. Jeandel. We prove a similar result for quasiperiodic shifts and also show that there exists a quasiperiodic shift of finite type for which Kolmogorov complexity of all patterns of size n\times n is \Omega(n).
Cite as

Bruno Durand and Andrei Romashchenko. On the Expressive Power of Quasiperiodic SFT. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{durand_et_al:LIPIcs.MFCS.2017.5,
  author =	{Durand, Bruno and Romashchenko, Andrei},
  title =	{{On the Expressive Power of Quasiperiodic SFT}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.5},
  URN =		{urn:nbn:de:0030-drops-80985},
  doi =		{10.4230/LIPIcs.MFCS.2017.5},
  annote =	{Keywords: minimal SFT, tilings, quasiperiodicityIn this paper we study the shifts, which are the shift-invariant and topologically closed sets of configurations}
}
Document
DOI: 10.4230/LIPIcs.STACS.2008.1334
Structural aspects of tilings

Authors: Alexis Ballier, Bruno Durand, and Emmanuel Jeandal

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
In this paper, we study the structure of the set of tilings produced by any given tile-set. For better understanding this structure, we address the set of finite patterns that each tiling contains. This set of patterns can be analyzed in two different contexts: the first one is combinatorial and the other topological. These two approaches have independent merits and, once combined, provide somehow surprising results. The particular case where the set of produced tilings is countable is deeply investigated while we prove that the uncountable case may have a completely different structure. We introduce a pattern preorder and also make use of Cantor-Bendixson rank. Our first main result is that a tile-set that produces only periodic tilings produces only a finite number of them. Our second main result exhibits a tiling with exactly one vector of periodicity in the countable case.
Cite as

Alexis Ballier, Bruno Durand, and Emmanuel Jeandal. Structural aspects of tilings. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 61-72, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{ballier_et_al:LIPIcs.STACS.2008.1334,
  author =	{Ballier, Alexis and Durand, Bruno and Jeandal, Emmanuel},
  title =	{{Structural aspects of tilings}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{61--72},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1334},
  URN =		{urn:nbn:de:0030-drops-13343},
  doi =		{10.4230/LIPIcs.STACS.2008.1334},
  annote =	{Keywords: Tiling, domino, patterns, tiling preorder, tiling structure}
}
Document
DOI: 10.4230/DagSemRep.377
Centennial Seminar on Kolmogorov Complexity and Applications (Dagstuhl Seminar 03181)

Authors: Bruno Durand, Leonid A. Levin, Wolfgang Merkle, Alexander Shen, and Paul M. B. Vitanyi

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Bruno Durand, Leonid A. Levin, Wolfgang Merkle, Alexander Shen, and Paul M. B. Vitanyi. Centennial Seminar on Kolmogorov Complexity and Applications (Dagstuhl Seminar 03181). Dagstuhl Seminar Report 377, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{durand_et_al:DagSemRep.377,
  author =	{Durand, Bruno and Levin, Leonid A. and Merkle, Wolfgang and Shen, Alexander and Vitanyi, Paul M. B.},
  title =	{{Centennial Seminar on Kolmogorov Complexity and Applications (Dagstuhl Seminar 03181)}},
  pages =	{1--6},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{377},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.377},
  URN =		{urn:nbn:de:0030-drops-152578},
  doi =		{10.4230/DagSemRep.377},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact